Otimização Convexa: Além da Convexidade Básica: Preservação por Supremo Pontual

Embora a convexidade básica cubra somas e escalonamento, a preservação da convexidade através do supremo pontual é uma operação fundamental para construir funções convexas não triviais e estabelecer dualidade. Afirma que, mesmo tendo uma família ilimitadamente infinita de funções convexas, seu "envelope superior" permanece convexo. Esse elo permite analisar formas convexas complexas usando componentes lineares simples.

1. A Definição Técnica

Para uma família de funções $\{f(\cdot, y) \mid y \in \mathcal{A}\}$, o supremo pontual é definido como:

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y)$$

O domínio desta função é o conjunto de pontos onde todas as funções da família estão definidas e o supremo é finito:

$$\text{dom } g = \{x \mid (x, y) \in \text{dom } f \text{ para todo } y \in \mathcal{A}, \sup_{y \in \mathcal{A}} f(x, y) < \infty\}$$

A Perspectiva do Epigrafico

Geometricamente, o epigrafico da função supremo é a intersecção dos epigraficos individuais:

$$\text{epi } g = \bigcap_{y \in \mathcal{A}} \text{epi } f(\cdot, y)$$

Como cada epigrafico individual é um conjunto convexo (devido à convexidade de $f(x, y)$ em $x$), e a intersecção de qualquer número de conjuntos convexos é ela mesma convexa, a convexidade de $g(x)$ é garantida.

2. Exemplos Significativos

Função Suporte: $S_C(y) = \sup \{ y^T x \mid x \in C \}$. Esta função é sempre convexa, independentemente de o conjunto $C$ ser convexo ou não, porque é o supremo de funções lineares (afins) de $y$.
Distância ao Ponto Mais Distante: $f(x) = \sup_{y \in C} \|x - y\|$. Mesmo para um conjunto $C$ de forma irregular, $f(x)$ é convexa em $x$ porque a norma é uma função convexa de $x$.
Maior Autovalor: Para uma matriz simétrica $X$, $f(X) = \lambda_{\max}(X)$ é convexa. Isso é derivado do quociente de Rayleigh: $\lambda_{\max}(X) = \sup\{y^T X y \mid \|y\|_2 = 1\}$. É o supremo de funções lineares de $X$.

Teorema: Representação por Funções Afins

Teorema

Quase toda função convexa pode ser expressa como o supremo pontual de uma família de funções afins (subestimadores globais).

Intuição

Em cada ponto $x_0$, uma função convexa $f$ possui um hiperplano suporte (uma função afim $h(x) = f(x_0) + g^T(x-x_0)$). Ao tomar o supremo de todos esses hiperplanos suporte, reconstruímos exatamente a função $f$.

🎯 Princípio Central

O supremo pontual preserva a convexidade e o ínfimo pontual preserva a concavidade. Este é o segredo por trás da convexidade de normas, funções espectrais e problemas duais.

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y) \implies g \text{ é convexa se } f(\cdot, y) \text{ for convexa } \forall y$$

PERGUNTA 1

Se $f_1(x), f_2(x), \dots, f_n(x)$ forem funções convexas, o que podemos dizer sobre $g(x) = \max\{f_1(x), \dots, f_n(x)\}$?

$g(x)$ é sempre convexa.

$g(x)$ é convexa apenas se todas as $f_i$ forem lineares.

$g(x)$ é côncava.

$g(x)$ é apenas quasiconvexa.

PERGUNTA 2

A função suporte $S_C(y) = \sup_{x \in C} y^T x$ é convexa em $y$ mesmo que $C$ seja um conjunto não convexo. Por quê?

Porque $y^T x$ é linear (e, portanto, convexa) em $y$ para qualquer $x$ fixo.

Porque o conjunto $C$ é automaticamente tratado como sua envoltória convexa.

Porque o produto interno é sempre uma função positiva.

As funções suporte são convexas apenas se $C$ for limitado.

PERGUNTA 3

Qual é a relação entre o epigrafico de $g(x) = \sup f_i(x)$ e os epigraficos individuais $\text{epi } f_i$?

$\text{epi } g = \bigcap \text{epi } f_i$

$\text{epi } g = \bigcup \text{epi } f_i$

$\text{epi } g = \text{conv}(\bigcup \text{epi } f_i)$

Não há relação direta.

PERGUNTA 4

A norma espectral de uma matriz $\|X\|_2 = \sigma_{\max}(X)$ é convexa porque...

É o supremo das funções convexas $\|Xv\|_2$ sobre vetores unitários $v$.

A soma dos valores singulares é sempre convexa.

Todas as normas são funções lineares.

Funções matriciais são sempre convexas no cone semi-definido positivo.

PERGUNTA 5

Se tomarmos o ínfimo pontual de uma família de funções côncavas, qual é o resultado?

Uma função côncava.

Uma função convexa.

Uma função linear.

Depende do domínio.

Desafio: Dualidade e Funções Conjugadas

MATH008 Análise Avançada

Na análise convexa, a função conjugada $f^*$ é definida via o supremo pontual de funções afins: $f^*(y) = \sup_x (y^T x - f(x))$. Essa transformação é vital para problemas de otimização dual.

[Resposta Curta] Condição de segunda ordem para convexidade. Prove que uma função duas vezes diferenciável $f$ é convexa se e somente se seu domínio for convexo e $\nabla^2 f(x) \succeq 0$ para todo $x \in \mathbf{dom} f.

Solução: Ao restringir $f$ a uma linha arbitrária $g(t) = f(x + tv)$, a convexidade de $f$ é equivalente a $g''(t) \geq 0$ para todo $v$ e todo $t$ tal que $x+tv \in \text{dom } f$. Como $g'(t) = \nabla f(x + tv)^T v$ e $g''(t) = v^T \nabla^2 f(x + tv) v$, a condição $g''(t) \geq 0$ para todo $v$ é equivalente à matriz Hessiana ser positiva semidefinida: $\nabla^2 f(x) \succeq 0$.

[Resposta Curta] Gradiente e Hessiana da função conjugada. Suponha que $\bar{y}$ e $\bar{x}$ estejam relacionados por $\bar{y} = \nabla f(\bar{x})$, e que $\nabla^2 f(\bar{x}) \succ 0$. (a) Mostre que $\nabla f^*(\bar{y}) = \bar{x}$. (b) Mostre que $\nabla^2 f^*(\bar{y}) = \nabla^2 f(\bar{x})^{-1}. (Saída Obrigatória: 250 palavras)

Resposta de Referência do Instrutor: Para abordar a parte (a), lembramos a definição da função conjugada $f^*(y) = \sup_x (y^T x - f(x))$. Para um $y = \bar{y}$ fixo, se $f$ for diferenciável e convexa, o supremo é alcançado no ponto onde o gradiente da função objetivo $h(x) = \bar{y}^T x - f(x)$ se anula. Estabelecendo $\nabla_x (\bar{y}^T x - f(x)) = 0$ obtemos $\bar{y} = \nabla f(x)$. Dado que o problema afirma $\bar{y} = \nabla f(\bar{x})$, segue-se que $\bar{x}$ é o maximizador. Pela propriedade da função conjugada no ponto de otimalidade, temos $f^*(\bar{y}) = \bar{y}^T \bar{x} - f(\bar{x})$. Derivando ambos os lados em relação a $\bar{y}$ e aplicando o teorema do envelope (ou o fato de $\bar{x}$ ser o otimizador), obtemos $\nabla f^*(\bar{y}) = \bar{x}$. Isso confirma que o gradiente da função conjugada atua como mapeamento inverso do gradiente da função original.

For part (b), we differentiate the relationship $\nabla f^*(\nabla f(x)) = x$ with respect to $x$ using the chain rule. This gives $\nabla^2 f^*(\nabla f(x)) \cdot \nabla^2 f(x) = I$, where $I$ is the identity matrix. Substituting $\bar{y} = \nabla f(\bar{x})$, we get $\nabla^2 f^*(\bar{y}) \cdot \nabla^2 f(\bar{x}) = I$. Since we are given $\nabla^2 f(\bar{x}) \succ 0$, the Hessian is invertible. Thus, $\nabla^2 f^*(\bar{y}) = [\nabla^2 f(\bar{x})]^{-1}$. This elegant result shows that the local curvature of the conjugate function is the reciprocal (or inverse matrix) of the curvature of the original function at corresponding points. This relationship is central to the analysis of Newton-type methods in dual space and the understanding of Legendre transforms in physics and optimization.